;; https://projecteuler.net/problem=24

;; Lexicographic permutations

;; Problem 24

;; A permutation is an ordered arrangement of objects. For
;; example, 3124 is one possible permutation of the digits
;; 1, 2, 3 and 4. If all of the permutations are listed
;; numerically or alphabetically, we call it lexicographic
;; order. The lexicographic permutations of 0, 1 and 2 are:

;; 012   021   102   120   201   210

;; What is the millionth lexicographic permutation of the
;; digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?


(import
 (except (rnrs base) let-values map)
 (only (guile)
       lambda* λ)
 (srfi srfi-1)  ; list stuff
 (srfi srfi-69)  ; hash tables
 (contract)
 (prefix (lib math) math:))


;; 0123456789 + 9   (9*1)
;; 0123456798 + 81  (9*9)
;; 0123456879 + 18  (9*2)
;; 0123456897 + 81  (9*9)
;; 0123456978 + 9   (9*1)
;; 0123456987 + 702 (9*9*9 - 9*3 = 9*78)
;; 0123457689 ...

;; There seems to be some pattern there, but not sure what
;; it is exactly.

(define check
  (λ (num)
    (or
     ;; Assuming the number is smaller than the biggest
     ;; number with leading 0. Then the number must not
     ;; contain a 0 elsewhere and of course all digits need
     ;; to be unique.
     (and (math:digits-unique? num)
          (not (member 0 (math:digits num))))
     ;; When the number is greater than the last number,
     ;; which has the 0 at the leading position, the
     ;; number is allowed to have a 0 at any place, as
     ;; long as all digits are still unique.
     (and (> num 0987654321)
          (math:digits-unique? num)))))

(define calc
  (λ (limit)
    (let iter ([permutations-found 1]
               [num 123456789])
      (cond
       [(= permutations-found limit) num]
       [(check (+ num 1))
        (iter (+ permutations-found 1) (+ num 1))]
       [else
        (iter permutations-found (+ num 1))]))))


(simple-format (current-output-port)
               "~a\n"
               (calc (expt 10 6)))
